/*
 * search.c
 *
 *  Created on: Apr 16, 2013
 *      Author: locpm
 */
#include "extglobals.h"
#include "protos.h"
#include "board.h"
#include "timer.h"
#include "stdio.h"
#include "move.h"
#include <string.h>

MOVE think()
{
	// This is the entry point for search

	int score, legalmoves, currentdepth;
	MOVE singlemove;

	//	===========================================================================
	//	Check if the game has ended, or if there is only one legal move,
	//  because then we don't need to search:
	//	===========================================================================
	if (isEndOfgame(&legalmoves, &singlemove))
		return NOMOVE;

	if (legalmoves == 1)
	{
		printf("forced move: ");
		displayMove(singlemove);
		printf("\n");

		return singlemove;
	}

	//	===========================================================================
	//	There is more than legal 1 move, so prepare to search:
	//	===========================================================================
	board.lastPVLength = 0;
	memset(board.lastPV, 0 , sizeof(board.lastPV));
	memset(board.whiteHeuristics, 0, sizeof(board.whiteHeuristics));
	memset(board.blackHeuristics, 0, sizeof(board.blackHeuristics));
	board.inodes = 0;
	// display console header
	displaySearchStats(1, 0, 0);
	initTimer(&board.timer);
	board.msStart = getMSTimer(&board.timer);

	//  iterative deepening:
	for (currentdepth = 1; currentdepth <= board.searchDepth; currentdepth++)
	{
		//  clear the buffers:
		memset(board.moveBufLen, 0, sizeof(board.moveBufLen));
		memset(board.moveBuffer, 0, sizeof(board.moveBuffer));
		memset(board.triangularLength, 0, sizeof(board.triangularLength));
		memset(board.triangularArray, 0, sizeof(board.triangularArray));
		board.followpv = TRUE;
		score = alphabetapvs(0, currentdepth, -LARGE_NUMBER, LARGE_NUMBER);
		board.msStop = getMSTimer(&board.timer);
		displaySearchStats(2, currentdepth, score);
		// stop searching if the current depth leads to a forced mate:
		if ((score > (CHECKMATESCORE-currentdepth)) || (score < -(CHECKMATESCORE-currentdepth)))
			currentdepth = board.searchDepth;
	}

	return (board.lastPV[0]);
}

int minimax(int ply, int depth)
{
	// Negamax

	int i, j, val, best;
	best = -LARGE_NUMBER;

	if (depth == 0) return eval();
	board.moveBufLen[ply + 1] = movegen(board.moveBufLen[ply]);
	for (i = board.moveBufLen[ply]; i < board.moveBufLen[ply + 1]; i++)
	{
		makeMove(board.moveBuffer[i]);
		{
			if (isTwoKingsFaceToFace() || isOtherKingAttacked())
				unMakeMove(board.moveBuffer[i]);
			else
			{
				board.inodes++;
				if (!ply)
					displaySearchStats(3, ply, i);

				val = -minimax(ply + 1, depth - 1); // note the minus sign
				unMakeMove(board.moveBuffer[i]);
				if (val > best) // both sides want to maximize from *their* perspective
				{
					best = val;
					board.triangularArray[ply][ply] = board.moveBuffer[i];					// save this move
					for (j = ply + 1; j < board.triangularLength[ply + 1]; j++)
					{
						board.triangularArray[ply][j] = board.triangularArray[ply + 1][j];	// and append the latest best PV from deeper plies
					}
					board.triangularLength[ply] = board.triangularLength[ply + 1];
					if (!ply)
					{
						board.msStop = getMSTimer(&board.timer);
						displaySearchStats(2, depth, val);
					}
				}
			}
		}
	}

	return best;
}

int alphabeta(int ply, int depth, int alpha, int beta)
{
	// Negascout

	int i, j, val;
	board.triangularLength[ply] = ply;

	if (depth == 0)
		return eval();

	board.moveBufLen[ply+1] = movegen(board.moveBufLen[ply]);

	for (i = board.moveBufLen[ply]; i < board.moveBufLen[ply+1]; i++)
	{
		makeMove(board.moveBuffer[i]);
		{
			if (isTwoKingsFaceToFace() || isOtherKingAttacked())
				unMakeMove(board.moveBuffer[i]);
			else
			{
				board.inodes++;
				if (!ply) displaySearchStats(3, ply, i);
				val = -alphabeta(ply+1, depth-1, -beta, -alpha);
				unMakeMove(board.moveBuffer[i]);
				if (val >= beta)
				{
					return beta;
				}
				if (val > alpha)
				{
					alpha = val;												// both sides want to maximize from *their* perspective
					board.triangularArray[ply][ply] = board.moveBuffer[i];					// save this move
					for (j = ply + 1; j < board.triangularLength[ply + 1]; j++)
					{
						board.triangularArray[ply][j] = board.triangularArray[ply+1][j];	// and append the latest best PV from deeper plies
					}
					board.triangularLength[ply] = board.triangularLength[ply + 1];
					if (!ply)
					{
						board.msStop = getMSTimer(&board.timer);
						displaySearchStats(2, depth, val);
					}
				}
			}
		}
	}

	return alpha;
}

int alphabetapvs(int ply, int depth, int alpha, int beta)
{
	// PV search

	int i, j, movesfound, pvmovesfound, val;
	board.triangularLength[ply] = ply;

	if (depth == 0)
	{
		board.followpv = FALSE;
		return eval();
	}

	movesfound = 0;
	pvmovesfound = 0;
	board.moveBufLen[ply+1] = movegen(board.moveBufLen[ply]);
	for (i = board.moveBufLen[ply]; i < board.moveBufLen[ply+1]; i++)
	{
		selectmove(ply, i, depth, board.followpv);
		makeMove(board.moveBuffer[i]);
		{
			if (isTwoKingsFaceToFace() || isOtherKingAttacked())
				unMakeMove(board.moveBuffer[i]);
			else
			{
				board.inodes++;
				movesfound++;
				if (!ply) displaySearchStats(3, ply, i);
				if (pvmovesfound)
				{
					val = -alphabetapvs(ply+1, depth-1, -alpha-1, -alpha);
					if ((val > alpha) && (val < beta))
					{
						val = -alphabetapvs(ply+1, depth - 1, -beta, -alpha);   // In case of failure, proceed with normal alphabeta
					}
				}
				else val = -alphabetapvs(ply+1, depth-1, -beta, -alpha);	    // Normal alphabeta
				unMakeMove(board.moveBuffer[i]);

				if (val >= beta)
				{
					// update the history heuristic
					if (board.nextMove)
						board.blackHeuristics[getFrom(board.moveBuffer[i])][getTosq(board.moveBuffer[i])] += depth*depth;
					else
						board.whiteHeuristics[getFrom(board.moveBuffer[i])][getTosq(board.moveBuffer[i])] += depth*depth;

					return beta;
				}

				if (val > alpha)
				{
					alpha = val;								    // both sides want to maximize from *their* perspective
					pvmovesfound++;
					board.triangularArray[ply][ply] = board.moveBuffer[i];					// save this move
					for (j = ply + 1; j < board.triangularLength[ply+1]; j++)
					{
						board.triangularArray[ply][j] = board.triangularArray[ply+1][j];	// and append the latest best PV from deeper plies
					}
					board.triangularLength[ply] = board.triangularLength[ply+1];
					if (!ply)
					{
						board.msStop = getMSTimer(&board.timer);
						displaySearchStats(2, depth, val);
					}
				}
			}
		}
	}

	// update the history heuristic
	if (pvmovesfound)
	{
		if (board.nextMove)
			board.blackHeuristics[getFrom(board.triangularArray[ply][ply])][getTosq(board.triangularArray[ply][ply])] += depth*depth;
		else
			board.whiteHeuristics[getFrom(board.triangularArray[ply][ply])][getTosq(board.triangularArray[ply][ply])] += depth*depth;
	}

	//	===========================================================================
	//	Checkmate/stalemate detection:
	//	===========================================================================
	if (!movesfound)
		return (-CHECKMATESCORE+ply-1);

	return alpha;
}

void displaySearchStats(int mode, int depth, int score)
{
	// displays various search statistics
	// only to be used when ply = 0
	// mode = 1 : display header
	// mode = 2 : display full stats, including score and latest PV
	// mode = 3 : display current root move that is being searched
	//			  depth = ply, score = loop counter in the search move list

	int i;
	U64 dt, hh, mm, ss;

	switch (mode)
	{
	case 1:
		printf("depth  score   nodes     time  knps PV\n");
		break;

	case 2:
		dt = board.msStop - board.msStart;

		// depth
		printf("%5d ", depth);

		// score
		printf("%+6.2f ", score/100.0);

		// nodes searched
		if      (board.inodes > 100000000) printf("%6.0f%c ", board.inodes/1000000.0, 'M');
		else if (board.inodes > 10000000)	 printf("%6.2f%c ", board.inodes/1000000.0, 'M');
		else if (board.inodes > 1000000)	 printf("%6.0f%c ", board.inodes/1000.0,    'K');
		else if (board.inodes > 100000)	 printf("%6.1f%c ", board.inodes/1000.0,    'K');
		else if (board.inodes > 10000)	 printf("%6.2f%c ", board.inodes/1000.0,    'K');
		else						 printf("%7"PRINTF_INT64_MODIFIER"u ", board.inodes);

		// search time
		if (dt > 3600000)
		{
			hh = dt/3600000;
			mm = (dt - 3600000*hh)/60000;
			ss = (dt - 3600000*hh - 60000*mm)/1000;
			printf("%02"PRINTF_INT64_MODIFIER"u%c", hh, ':');
			printf("%02"PRINTF_INT64_MODIFIER"u%c", mm, ':');
			printf("%02"PRINTF_INT64_MODIFIER"u ", ss);
		}
		else if (dt > 60000)
		{
			mm = dt/60000;
			ss = (dt - 60000*mm)/1000;
			printf("   %02"PRINTF_INT64_MODIFIER"u%c", mm, ':');
			printf("%02"PRINTF_INT64_MODIFIER"u ", ss);
		}
		else if (dt > 10000)		printf(" %6.1f%c ", dt/1000.0, 's');
		else if (dt > 1000)			printf(" %6.2f%c ", dt/1000.0, 's');
		else if (dt > 0)			printf(" %5"PRINTF_INT64_MODIFIER"u%s ", dt, "ms");
		else						printf("     0%s ", "ms");

		// search speed
		if (dt > 0) printf("%5"PRINTF_INT64_MODIFIER"u ", board.inodes/dt);
		else		printf("    - ");

		// store this PV:
		rememberPV();

		// PV
		for (i = 0; i < board.triangularLength[0]; i++)
		{
			displayMove(board.triangularArray[0][i]);
			printf(" ");
		}
		printf("\n");
		break;

	case 3:
		printf("%12s (%2d/%2d)%16s", " ", score+1, board.moveBufLen[depth+1]-board.moveBufLen[depth], " ");
		displayMove(board.moveBuffer[score + board.moveBufLen[depth]]);
		printf("...\r");
		break;

	default: break;
	}

	return;
}

BOOL isEndOfgame(int *legalmoves, MOVE *singlemove)
{
	// Checks if the current position is end-of-game due to:
	// checkmate, stalemate


	// are we checkmating the other side?
	if (isTwoKingsFaceToFace() || isOtherKingAttacked())
	{
		if (board.nextMove)
			printf("1-0 {White wins}\n");
		else
			printf("0-1 {Black wins}\n");

		return TRUE;
	}

	// how many legal moves do we have?
	int i;
	(*legalmoves) = 0;
	board.moveBufLen[0] = 0;
	board.moveBufLen[1] = movegen(board.moveBufLen[0]);
	for (i = board.moveBufLen[0]; i < board.moveBufLen[1]; i++)
	{
		makeMove(board.moveBuffer[i]);
		if (!isTwoKingsFaceToFace() && !isOtherKingAttacked())
		{
			(*legalmoves)++;
			singlemove->moveInt = board.moveBuffer[i].moveInt;
		}
		unMakeMove(board.moveBuffer[i]);
	}

	// checkmate or stalemate?
	if (!(*legalmoves))
	{
		if (board.nextMove)
			printf("1-0 {White wins}\n");
		else
			printf("0-1 {Black wins}\n");

		return TRUE;
	}

	return FALSE;
}

void rememberPV()
{
       // remember the last PV
       int i;
       board.lastPVLength = board.triangularLength[0];
       for (i = 0; i < board.triangularLength[0]; i++)
       {
    	   board.lastPV[i] = board.triangularArray[0][i];
       }
}
